/*
 * @(#)Algorithms.java	1.3 08/31/11
 *
 * Copyright 2011 Ice Spring All rights reserved.
 * Mrogrape/Javaliang.com PROPRIETARY.
 */
package com.mrogrape.util;

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;


/**
 * 此类提供一些实用的方法以完成一些需要特殊算法的操作。
 * 
 * @author  Ice Spring 
 * @version 1.3.20110831
 */
public class Algorithms {

	/**
	 * 从0（包含）到最大值（不包含）范围内抽出一定数目的 不重复的伪随机数,此方法已经
	 * 优化算法效率。
	 * 
	 * @param maxValue 取值范围的最大值
	 * @param quantity 需要取出的随机数的数量
	 * @return         获取的伪随机数
	 */
	public static int[] getRandoms(int maxValue, int quantity) {
		if(quantity>maxValue){
			throw new IllegalArgumentException("Quantity must be less than max value");
		}
		int[] re = new int[quantity];
		boolean[] hash = new boolean[maxValue];
		Random rand = new Random();

		for(int i = 0 ; i < quantity ;){
			int temp = rand.nextInt(maxValue);
			if(hash[temp]!=true){
				re[i++]=temp;
				hash[temp] = true;
			}
		}
		return re;
	}

	/**
	 * 通过MD5加密算法对一个字符串(一般是密码)进行加密。
	 * 
	 * <p>
	 * 此方法仅提供有限的MD5加密支持，如果需要更加高级的MD5加密支持，请使用：
	 * {@link java.security.MessageDigest}。
	 * 
	 * @param input 需要加密的字符串
	 * @return      加密后的MD5码，如果当前JDK未提供MD5支持，则返回空串。
	 * @see         java.security.MessageDigest
	 */
	public static String md5encrypt(String input){

		MessageDigest md = null;
		try {
			md = MessageDigest.getInstance("MD5");
		} catch (NoSuchAlgorithmException e) {
			return "";
		}

		byte[] re = md.digest(input.getBytes());
		int length = re.length;

		char str[] = new char[length * 2];
		int k = 0;
		for (int i = 0; i < length; i++) {
			str[k++] = Algorithms.hexDigits[re[i] >> 4 & 0xf];
			str[k++] = Algorithms.hexDigits[re[i] & 0xf];

		}

		return new String(str);
	}

	private static final char hexDigits[] = { '0', '1', '2', '3', '4', '5', '6', '7', 
		'8', '9','a', 'b', 'c', 'd', 'e', 'f' };

	/**
	 * 对数组中的元素进行随机排序。
	 * 
	 * <p>
	 * 此方法采用以下策略来完成数组的排序：
	 * <ol>
	 * <li>创建一个Bucket,并把数组中全部的数据放入。
	 * <li>采用随机抽取的方式取出全部的数据，并放入一个有序List(ArrayList)中。
	 * <li>将此list中的数据回存入原始数组,然后返回。
	 * </ol>
	 * 因为桶采用Random类来提供随机抽取功能，所以此方法排序效率依赖于Random类。
	 * 经测试在数组大小小于10000时此方法具有理想的效率。
	 * 
	 * <p>
	 * <b>警告：</b>此方法会直接修改原数组。
	 * 
	 * @param <T>   需要排序的数组的类型。
	 * @param array 需要排序的数组。
	 * @return      排序完成的数组的引用。
	 * @see         com.mrogrape.util.Bucket
	 * @see         java.util.Random
	 */
	public static <T> T[] randomSort(T[] array){
		Bucket<T> container = new Bucket<T>();
		List<T> result = new ArrayList<T>();
		int length = array.length;

		for(T e : array){
			container.put(e);
		}

		for(int i = 0; i < length; i++){
			result.add(container.take());
		}

		return result.toArray(array);
	}


}



